package 高效制胜._10;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/17 17:07
 * 不邻接植花
 * 算法：集合  贪心
 * 由于有四种花可以选，而每一个花园最多能与三个花园相连
 * 把每个花园与之相连的花园都记录下来
 */
public class _1042 {
    public static void main(String[] args) {

    }

    public int[] gardenNoAdj(int n, int[][] paths) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] path : paths) {
            Set<Integer> list = map.getOrDefault(path[0], new HashSet<>());
            list.add(path[1]);
            map.put(path[0], list);
            list = map.getOrDefault(path[1], new HashSet<>());
            list.add(path[0]);
            map.put(path[1], list);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        for (int i = 1; i <= n; i++) if (map.containsKey(i)) dfs(i, map.get(i), ans);
        return ans;
    }
    void dfs(int idx, Set<Integer> list, int[] ans) {
        Set<Integer> used = new HashSet<>(4);
        for (Integer f : list) used.add(ans[f - 1]);
        List<Integer> flowers = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
        flowers.removeAll(used);
        ans[idx - 1] = flowers.get(0);
    }

}
